The present invention relates to finite state machines. In particular, the present invention relates to optimizing finite state machines.
Finite state machines are a general way of efficiently representing sets of strings, probability distributions on strings, mappings between strings, and joint and conditional distributions on pairs of strings. They are used in speech recognition for representing grammars, language models, dictionaries, search networks, and the search space during decoding. In natural language processing, they are used for parsing, morphological analysis, and tokenization.
Traditionally, finite state machines are directed networks composed of a set of nodes and a set of directed links between those nodes. One of the nodes is identified as an initial node and at least one, but possibly many other nodes are designated as valid final nodes. A valid pass through the finite state machine starts at the initial node, follows links through the network, and ends at a final valid node. Before reaching the final node, the path may pass through other final nodes. While it is legal to stop at a final node, a valid path does not have to stop simply because it reaches a final node.
Each link is labeled with symbols from an alphabet. For example, the links may be labeled with letters, phonemes, triphones, words, or some other abstract symbol. Thus, the finite state machine represents a set of strings, each of which is generated by some legal path through the finite state machine.
To determine if a given string is in the set of strings represented by the finite state machine, one starts at the initial node and follows all the links with labels that agree with the next symbol in the string, keeping track of the set of nodes that are passed through. This process continues until there is either no link from the current node that matches the next symbol, in which case the string does not parse, or until the string ends. If the string ends and the set of current nodes contain a final state, the string is represented by the finite state machine, and if not, the string is not represented by the finite state machine.
In some finite state machines, a cost or probability is placed on each link in addition to the label. Costs or probabilities are combined during the traversal of the path through the finite state machine to give the cost or probability of generating a string.
Finite state machines can either be finite state acceptors or finite state transducers. Finite state acceptors have input symbols on each link while finite state transducers have input and output symbols on each link. For example, a final link for a string that represents a word in a finite state transducer can have an input symbol for the last phoneme in the word and an output symbol representing the complete word.
One of the advantages of finite state machines is that they can be optimized to remove redundancies and thereby reduce the time and space required to use the finite state machines. One optimization process is known as determinization. Under determinization, an equivalent finite state machine is created such that there is at most one link with a given label leaving each node. This means that during parsing, there is only one current state at a time instead of a set of current states. Another optimization technique is known as minimization in which the finite state machine is reduced to produce the smallest number of states possible. The goal in minimization is to create a finite state machine with the fewest possible nodes and links for the set of strings represented by the finite state machine.
Classical optimization routines only consider labels on links. As such, it has not been possible to use classical routines to optimize finite state machines that include labels on nodes. This has meant that such finite state machines are either not optimized or that some special optimization routine must be written that tracks the node labels as well as the link labels. Thus, a system is needed that allows link-based optimization routines to be used with finite state machines that include node labels.